Binary Watch || Letter Combinations of a Phone Number

发表于

Binary Watch

Question

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

1
2
Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Analysis

简单的回溯问题，注意以下几点：

  • 递归过程中需要标明小时和分钟计算到了哪位数字，即hindex,mindex，否则生成重复时间
  • 利用HashSet排除重复的时间
  • 在插入过程中，所有h>=12和m>=60的情况都排除

LeetCode Discuss 简明做法

LeetCode Discuss 非回溯做法

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> res=new ArrayList<>();
        HashSet<String> table=new HashSet<>();
        if(num==0){
            res.add("0:00");
            return res;
        }
        helper(table,res,num,0,0,0,0);
        return res;
    }
    
    public void helper(HashSet<String> table, List<String> res, int n, int hour, int minute, int hindex, int mindex){
        if(n==0){
            StringBuilder tmp=new StringBuilder();
            if(hour>=12)
                return;
            tmp.append(Integer.toString(hour));
            tmp.append(":");
            if(minute>=60)
                return;
            if(minute<10){
                tmp.append("0");
            }
            tmp.append(Integer.toString(minute));
            if(!table.contains(tmp.toString())){
                table.add(tmp.toString());
                res.add(tmp.toString());
            }
            return;
        }
        for(int i=hindex;i<4;i++){
            helper(table,res,n-1,hour+(1<<i),minute,i+1,mindex);
        }
        for(int j=mindex;j<6;j++){
            helper(table,res,n-1,hour,minute+(1<<j),hindex,j+1);
        }
    }
}

Letter Combinations of a Phone Number

Question

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Example：

1
2
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Analysis

同上简单的回溯问题，利用String数组存储不同数字对应的字符串，注意：

  • 确认keys下标的时候 -‘0’
  • 初始判断是否digits长度为0

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    private static final String[] keys={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    
    public List<String> letterCombinations(String digits) {
       List<String> res=new ArrayList<>();
       if(digits.length()==0)   return res;
       helper("", 0, digits, res);
       return res;
    }
    
    public void helper(String prefix, int index, String digits, List<String> res){
        if(index>=digits.length()){
            res.add(prefix);
            return;
        }
        
        String tmp=keys[digits.charAt(index)-'0'];
        for(int i=0;i<tmp.length();i++){
            helper(prefix+tmp.charAt(i), index+1, digits, res);
        }
    }
}